package com.dmall.directed.graph;

import java.util.ArrayList;
import java.util.Collections;

/**
 * @author: xiao1.wang
 * @date: 2022/9/4 16:50
 */
public class TopoSort2 {

    private Graph G;
    private ArrayList<Integer> res;
    private final boolean hasCycle;

    public TopoSort2(Graph G) {
        if (!G.isDirected()) {
            throw new IllegalArgumentException("TopoSort2 only works in directed graph.");
        }

        this.G = G;
        this.res = new ArrayList<>();

        hasCycle = new DirectedCycleDetection(G).hasCycle();
        if (hasCycle) {
            return;
        }
        GraphDFS dfs = new GraphDFS(G);
        for (int v : dfs.post()) {
            res.add(v);
        }
        Collections.reverse(res);
    }

    public boolean hasCycle() {
        return hasCycle;
    }

    public ArrayList<Integer> result() {
        return res;
    }

    public static void main(String[] args) {
        String filename = TopoSort2.class.getClassLoader().getResource("com/dmall/directed/graph/ug.txt").getPath();
        Graph g = new Graph(filename, true);
        TopoSort2 topoSort = new TopoSort2(g);
        System.out.println(topoSort.hasCycle());
        System.out.println(topoSort.result());

        String filename2 = TopoSort2.class.getClassLoader().getResource("com/dmall/directed/graph/ug3.txt").getPath();
        Graph g2 = new Graph(filename2, true);
        TopoSort2 topoSort2 = new TopoSort2(g2);
        System.out.println(topoSort2.hasCycle());
        System.out.println(topoSort2.result());

        String filename3 = TopoSort2.class.getClassLoader().getResource("com/dmall/directed/graph/ug4.txt").getPath();
        Graph g3 = new Graph(filename3, true);
        TopoSort2 topoSort3 = new TopoSort2(g3);
        System.out.println(topoSort3.hasCycle());
        System.out.println(topoSort3.result());
    }
}
